Cellular automata, mobile automata, Turing machine, substitution system, sequential-substitution system, tag system, cyclic-tag system, register machine, and symbolic system can generate algorithms {algorithm generator}.
Programs {artificial life} can model reproduction, movements, or reactions.
Systems have positions {contour map}, at which variables are constant. Systems have contour series.
Feedback and feedforward controls systems {cybernetics}|. Systems have logical properties, control mechanisms, and communication patterns.
Running programs and analyzing results finds proofs and results {experimental mathematics} [Alexandrov et al., 1984] [Hersh, 1997].
Nested patterns are self-similar {fractal geometry}.
Systems theory {General Systems Theory}| can use calculus, compartment theory, control theory, cybernetics, decision theory, factor analysis, game theory, graph theory, information theory, network theory, operations research, queuing theory, set theory, simplex methods, stochastic modeling, and equation systems [Bertalanffy, 1928] [Bertalanffy, 1968] [Thurstone, 1935].
relations
Networks have interacting nodes. Relations among system objects can be strong or weak, linear or non-linear, and hierarchical or otherwise. Relations can involve progressive differentiation, action triggers, feedback, and adaptations.
strategies
Systems can have growth/stability, competition/cooperation, centralization/decentralization, and specialization/generalization.
Symbol strings can represent numbers and functions. Using functions on input function and data strings makes output function and data strings {lambda calculus}. Systems expressing lambda calculus make many new strings. Removing random, irregular, or long strings can keep number of strings constant, and system can evolve toward stable set of strings. One string can copy itself better than others and become more numerous than other strings {level-0 organization}. Removing strings that copy themselves causes one or more repeating string cycles {level-1 organization}.
Lorenz systems are like waterwheel {leaking waterwheel} with leaking buckets that receive more water regularly.
low flow
Adding small drops slowly does not move waterwheel, because buckets leak equal or more water than they receive. Force is not enough to overcome frictional force.
high flow
With bigger drops or higher dripping rate, waterwheel turns steadily. With even bigger drops or even higher rate, waterwheel eventually spins so fast that buckets do not get as much water and buckets do not lose as much water each turn. Then waterwheel slows non-linearly. Spin can reverse.
Non-equilibrium systems can oscillate {limit cycle, system}, rather than achieve steady state.
Linear equations {linear programming} can show how each factor {independent variable, linear programming} affects one output {dependent variable, linear programming}. Linear-equation sets can show how each factor affects each output.
purposes
Linear-equation sets can find optimum factor amounts and/or optimum output amounts.
factors
Factors are abstract-space dimensions. Factors can vary from zero to maximum amount. Factor amount marks position along factor spatial dimension.
simplex
In abstract space, connecting coordinates with lines, planes, and higher-dimension surfaces makes polyhedrons, centered on origin. Polyhedron vertices can be optimal or extreme solutions, showing how much factor to use {simplex method}. Extreme solutions can maximize output, maximize profit, maximize efficiency, and minimize cost.
methods
Analyzing extreme solutions uses marginal value. Optimization methods {sequential optimization method} can use slopes.
summation
Linear processing adds things of same kind and cannot model interactions between different things. Linear processing cannot transform data or reduce variable number, because sums have same dimensions as things added.
Numbers {Lyapunov exponent} can measure phase-space dimension extension, compression, or folding. If Lyapunov exponent is greater than zero, dimension extends. If Lyapunov exponent is less than zero, dimension compresses.
The most frequently used representations use shortest code {Minimum Description Length Principle}.
Systems can perform many similar processes simultaneously {parallel processing}|, using many independent processing paths. If process inputs or outputs go to other processes, system must have controls that coordinate signals in time and space. If parallel processes are redundant or can substitute for each other, system is more stable.
Processes {Post grammar} can replace input string with output string of same or different length. In simple Post grammars, short input strings have output strings listed in a lookup table {grammar table}. Complex Post grammars have long input and output strings, and rules determine output string substituted for input string. Rules are input strings. Rules can select input strings or string sequences. Rules can select or substitute strings deterministically or probabilistically. Post grammars can be equivalent to Turing machines and lambda calculi.
Propositions {preference rule} {preference condition} can have conditionals and conclusion.
conditionals
Conditionals are positive or negative statements. Conditionals can link by conjunction or disjunction.
process
Systems can have preference-rule sequences. Systems test preference rules in sequence and perform first satisfied rule. If system satisfies conditions, preference rule applies, conclusion is true, and action starts. If any condition is not true, or if information is lacking for one or more conditionals, preference rule does not apply, and system tests next proposition. If no preference rule applies, system uses default action.
All agents can communicate what they are doing to all other agents, and all agents decide what to do based on same goal or rule {receiver-based optimization}.
Two registers can have fixed lengths and two instructions {register machine}. 'increment' increases number in register by one. 'decrement-jump' decreases number in register by one and then goes to new program location.
Continuous equations can have discrete approximations {scientific computing}.
Annealing {simulated annealing} can use heating, then cooling, then heating, then cooling, and so on. Heating makes molecular structure more random. Cooling makes molecular structure less random. In simulated annealing, system first minimizes or maximizes, then relaxes to farther-away position. It then repeats cycle. For example, system can minimize cost {cooling}, but occasionally explore higher-cost outcomes to go outside local minima {heating}, because neighboring outcomes have similar costs.
Ants and other social animals act and react based on signal communication, and net result is that whole colony has behavior patterns {swarm intelligence}. Ants leave pheromone trails. Pheromone evaporates over time. Ants taking shorter trails go from nest to food, and vice versa, more often, leaving more pheromone. Higher pheromone concentration attracts more ants. As they consume food, ants have less excitement and leave less pheromone, and fewer ants take that path, allowing ants to move more randomly and find other food sources farther away.
Strings transform according to rules {symbolic system}.
Abstract machines {Turing machine} [Herken, 1988] [Turing, 1937] run algorithms that have finite numbers of elements (typically 0 and 1) and instructions to execute (rule) and use only rational numbers, countable irrational numbers, and rational approximations to irrational numbers. Turing machines have a tape, a tape reader/writer with an internal state, and rules.
tape
The tape contains all input and receives all output.
The tape has only 0 or 1 at each of an infinite number of tape positions. The tape has infinitely many 0 positions and at least one 1 position.
The tape holds the input data, rules, and output.
Tape position combinations represent numbers, text, number-and-text separator symbol (comma), number-and-text termination symbol (blank), minus sign, plus sign, division sign, move right one square, move left one square, read, write, and stop. For example, the tape position combination ...001100... can represent the decimal number 3, the letter C, or the symbol minus sign. Coding is unique and unambiguous.
Combinations of tape position combinations represent numbers, words, sentences, mathematical formulas, dates, and arrays. Coding can represent all rational numbers and can represent approximations to countable irrational numbers, using minus sign, plus sign, and division sign. However, most irrational numbers are not computable by Turing machine, which never stops if something is uncountable.
The tape starts with all input data and instructions on one tape-reader side. Input data and instructions make a finite binary number. Instructions and input data depend on each other.
The tape ends with all output data on one tape-reader side. Output data makes a finite binary number. The other tape side includes intermediate calculations, modified input data, and rules.
Note: Turing machines have no need for more than one tape or tape reader, because multiple ones are always equivalent to one.
tape reader/writer
The tape reader/writer reads the 0 or 1 at the current tape position and writes the same or opposite symbol there (overwriting the previous symbol).
After writing, the tape reader/writer changes to the same or another internal state.
After writing, the tape reader/writer moves right or left one tape position. It can eventually move to any tape position, and go there any number of times, but does not have to go all positions or any one tape position.
internal state
The internal state is a combination of previously read symbols and is a finite binary number. Turing machines have a finite number of internal states, to which it can return any number of times, but does not have to reach all states or any one internal state.
The internal state and the currently read symbol determine the rule to apply after reading. Therefore, each internal state has a pair of rules, one for reading 0 and one for reading 1. Turing machines never reach an internal state that has no rules.
rules
For the current internal state and currently read symbol, rules (instructions) determine what the tape reader/writer does after reading the tape symbol: 1. Keep the same, or change to a different, internal state. AND 2. Change, or do not change, the symbol at the tape position. AND 3. Move tape one position to right or left. AND 4. Stop or do not stop.
Rules depend on input data. The number of rules is two times the number of internal states. Turing machines have a finite number of rules (because they have a finite number of internal states). Rules are finite binary numbers.
Rules can repeat any number of times. Turing machines do not have to use all rules or any one rule.
Turing machines must be able to get to at least one stop rule and so end operation.
output
After a stop rule runs, the tape has output data to the left or right of the final tape position. The output is a number, symbol, letter, word, phrase, sentence, date, or boolean yes or no (or an array of them). The tape's other side has intermediate calculations, modified input data, and the rules.
Turing machines must have at least one 1 in an output-side tape position.
operation
The tape reader/writer starts in an internal state at a 0 tape position on the right or left side of the input-data-and-rules tape positions.
The tape reader/writer reads the 0 at that tape position and, using the rule for the internal state and the 0 symbol, changes to the same or another internal state, prints the same or opposite symbol at the same position, moves the tape one position to right or left, and stops or does not stop.
Next, the tape reader/writer reads the 0 or 1 symbol at the new tape position and, using the rule for the current internal state and read symbol, changes to the same or another internal state, prints the same or opposite symbol at the same position, moves the tape one position to right or left, and stops or does not stop.
The tape reader/writer then continues reading symbols and following rules until it comes to a stop, which it must do or else it is not a valid Turing machine.
After the stop rule, the answer is to the left or right of final tape position. The other tape side has intermediate calculations, modified input, and rules.
Turing machines begin with a finite binary number, for inputs and rules, and produce a finite binary number, for output.
restrictions
Turing machine must have at least one rule that leads to STOP, must not move to non-existent internal state, must use and make only coded sequences of marked and blank squares, and must have at least one marked square on output side.
It is difficult to make input data and rules that reach STOP and so make Turing machines.
universal Turing machine
Some Turing machines (universal Turing machine), with special input data and rules on the tape, can imitate any Turing machine.
A simple cellular automaton and a special initial state can make a universal Turing machine.
computers and Turing machines
Computers are efficient universal Turing machines.
brains and Turing machines
Rather than one tape reader/writer, brains have many readers and writers acting continually and simultaneously. Upstream neurons automatically write to downstream neurons. Downstream neurons automatically read upstream neurons.
Rather than serial processing, neurons update simultaneously.
Rather than reading or writing one tape position at a time, brains continually and simultaneously read and write to all neurons.
Rather than separate tape positions, neurons interact.
Rather than a tape with an infinite number of positions, brains use a three-dimensional region with a finite number of locations.
Rather than two symbols to read, neuron synapses have synaptic strengths, which change continually.
Rather than two symbols to write, neurons send impulse rates, which change continually.
Rather than one internal state, brains have many internal states. Each neuron has a state, and each neuron set has a state. Brain, neuron set, and neuron internal states are complex and interact.
Rather than a small fixed set of rules, brains use many and more complex rules for changing state, reading, writing, moving, and stopping, and rules can interact and change.
Rather than stopping at a STOP rule, brains stop consciousness when they fall asleep but still process information.
Rather than the ability to perform any algorithm with a finite number of elements and instructions, brains may not be able to perform some algorithms, can perform non-algorithmic functions, and can use an infinite number of elements and instructions.
equivalences
Turing machines can compute partial recursive functions that use recursively enumerable element sets. Turing machines can approximate functions that are not partial recursive functions with partial recursive functions.
Because quantitative grammars involve only integers, Turing machines can be equivalent to quantitative grammars, Post grammar, and lambda calculus.
example 1: Turing Machine with One State, Two Rules, and One Marked Square
Rule 1: If State 1 and unmarked square, change to internal state 1, do not change the mark, move tape one square to right, and do not stop. Rule 2: If State 1 and marked square, change to internal state 1, do not change the mark, move tape one square to right, and stop. For example, see Figure 1 through Figure 5.
example 2: Turing Machine with Two States, Three Rules, and Two Marked Squares
Example Turing machine can calculate 1 + 1 = 2 or 01 + 01 = 10 in binary code. Infinite tape has square series that define rules. Then it has square series that define input: 0s, up to 1, followed by 1, and then 0s: ...00000110000... Reader starts to right of rules, reads rules, and ends to right of rules and left of the ...11..., in internal state 0. Rules for this Turing machine are as follows. If current state is 0, and 0 is read, move right to next input. If current state is 0, and 1 is read, move right to next input and add 1 to state. If current state is 1, and 1 is read, move left to next input and add 1 to state and stop. To tape-reader right is the answer 10.
example 3: Turing Machine with Two States, Four Rules, and Two Marked Squares
Example Turing machine can calculate 1 + 1 = 2 or 01 + 01 = 10 in binary code. Infinite tape has square series that define rules. Then it has square series that define input: 0s, up to 1, followed by 0, followed by 1, and then 0s: ...000001010000... Reader starts to right of rules, reads rules, and ends to right of rules and left of the ...101..., in internal state 0. Rules for this Turing machine are as follows. If current state is 0, and 0 is read, move right to next input. If current state is 0, and 1 is read, move right to next input and add 1 to state. If current state is 1, and 0 is read, move right to next input. If current state is 1, and 1 is read, move left to next input and add 1 to state and stop. To tape-reader right is the answer 10.
Cells can update state at each step according to current state and neighboring-cell states {cellular automaton}|. Automata can have tapes with more than one dimension, with Turing machines at tape segments {node, tape segment}. Cells can have only one state and interact only with neighbors. Combining state and neighbor states determines cell next state [Wolfram, 2002].
For fixed cell number, one cell can have one state and update at each step, and system can move to another cell {mobile automaton}, according to neighboring cell states.
Heating fluid at container bottom results in rising and swirling motion {convection, non-linear} {non-linear convection}.
warm
If hot fluid rises very slowly into cooler fluid, it can transfer heat by contact faster than by convection, and fluid at top becomes hotter and less dense, preventing hot fluid from rising. Density difference causes force, but force is not enough to overcome viscous force.
hot
If hot fluid rises smoothly into cooler fluid, heat transfers mostly by convection, cooler fluid sinks as hot fluid rises, and hot fluid cools when it reaches top, so smooth flow goes upward in center and downward at edges.
If hot fluid rises so quickly that it has lost little heat when it reaches cooler-fluid top, and it does not get as much heat from burner, it eventually slows flow rate {deterministic non-periodic flow}. Then system {Lorenz system} slows non-linearly. Non-linear behavior never repeats but is periodic around central points {Lorenz attractor} in multidimensional-variable space.
Non-linear systems {non-linear system} have terms that are multiplicative, not additive. For example, Navier-Stokes fluid-dynamics equation is non-linear. From some states, complex non-linear systems oscillate, but not perfectly, so they never repeat same state. Complex non-linear systems always have states, times, and locations from which they are unstable.
Soliton equations have non-linear dynamics {non-linear dynamics}.
Starting with a number of cells, all cells can have one state. Cells replace cells according to neighboring states {substitution system}.
Starting with a number of cells, all cells can have one state. Cells replace first cells reached by search, according to neighboring states {sequential substitution system}.
In a fixed number of cells, all cells can have one state. System removes cells at one end and adds cells at other end {tag system}, depending on cells removed.
In a fixed number of cells, all cells can have one state. System removes cells at one end and adds cells at other end {cyclic tag system}, depending on cells removed.
Programs {artificial intelligence}| (AI) can embody logical processes and have memory. Artificial-intelligence systems have sets {knowledge base} {database} of classes or representations. Reasoning methods {control strategy} select rule or representation, check rule conditions, and track used and available rules. AI has rule {operation} sets. AI has search mechanisms {graph search}, which apply rule at nodes to get to new nodes. Rules or predicates have attributes, sets, objects, events, values, or subsets.
Artificial-intelligence systems {expert system}| can mimic experts. Expert systems can store rules with which to classify. Expert systems can make decisions based on utility-function optimization. Expert systems can use networks with weighted connections. Sets of IF/THEN statements can make output from input.
Systems {inquiring system} have boundaries, communication methods, goals, and comparison methods, such as distinguishing or generalizing. Systems modify based on success or failure, build language, have memory, take perspective, change perspective, make models, and observe self.
Catastrophes {catastrophe theory}| are space discontinuities [Thom, 1968] [Thom, 1972] [Waddington, 1968] [Woodcock and Davis, 1978]. Discontinuity type depends on dimension number. Number of parameters determines how many system states are possible. Actual behavior depends on present state and past history.
transformations
Spaces with four or less dimensions allow seven discontinuous transformations: fold, cusp, swallowtail, butterfly, parabolic umbilic, elliptic umbilic, and hyperbolic umbilic. No other catastrophe types are possible. Discontinuities can appear in continuous-equation systems.
Folds make a discontinuity line between two planes {fold catastrophe}. It involves one dimension and only one state. From fold point, either stable or unstable behavior can happen.
Folds along two dimensions make two discontinuity lines, which meet at a point between three planes {cusp catastrophe}. From meeting-point state, states can diverge on both folds, with no middle behavior between the states. Different positions and directions make different state changes {hysteresis, catastrophe}.
Folds along four dimensions make four discontinuity lines, which meet at a point between five planes {butterfly catastrophe}.
Folds along three dimensions make three discontinuity lines, which meet at a point between four planes {swallowtail catastrophe}.
Folds along three dimensions make three discontinuity lines, which meet at a line {elliptic umbilic catastrophe}. It involves three dimensions and only two states.
Folds along three dimensions make three discontinuity lines, which meet at a line {hyperbolic umbilic catastrophe}. It involves three dimensions and only two states.
Folds along four dimensions make four discontinuity lines, which meet at a surface {parabolic umbilic catastrophe}. It involves four dimensions and only two states.
Even complex systems have parts with simple processes. Chaotic systems have parts with no chaos. Small initial-condition changes can cause large result changes {chaos theory}| [Lorenz, 1963].
Non-linear complex systems are sensitive to initial conditions, as if butterfly flight in one place affects weather pattern in another place {butterfly effect}| [Gleick, 1987] [Prigogine and Nicolis, 1989] [Prigogine and Stengers, 1984] [Prigogine, 1980] [Ruelle and Takens, 1971] [Ulam, 1976] [Li and Yorke, 1975].
Systems can have processes that regularly repeat {periodicity}|. Increased repetition rate {period doubling} or system size can lead to chaos, as wavelength and space decrease. Systems can make matter or energy pulses {intermittency}. Systems can have periods that are not exact {quasiperiodicity}. Energy or mass dissipation cancels or removes conflicting motions and results in changes along one dimension. Periodicity is only in that dimension.
Systems can have many and/or different states, objects, events, dependencies, and interactions {complexity, system}. Complex systems share information among objects [Goodwin, 1994] [Kauffman, 1993] [May, 1976] [Pagels, 1988] [Prigogine and Nicolis, 1989] [Prigogine and Stengers, 1984] [Prigogine, 1980] [Smale, 1967].
hierarchy
Having more parts and relations allows part and relation levels.
emergence
Having more parts and relations allows new part and relation combinations.
laws
The many and varied complex-system relations make conservation laws, constancies, covarying elements, and other regularities.
flows and circuits
The many complex-system relations propagate changes throughout system.
states
Systems can return to initial or previous state or reach terminal state, so system halts or repeats. Terminal states are typically undesirable, unstable, or otherwise break system, so system must protect against them. Physical complex systems can self-destruct. They must have mechanisms to prevent halting, repeating, and breakdown or extricate themselves from such situations. Complex systems typically are stable for only some states. Stable complex systems have resting or default states.
non-isolation
Complex systems can have complex input and output.
non-isolation: energy
Stable physical complex systems require energy sources and regulate energy input and output between system and environment.
non-isolation: environment
Physical complex systems can work in only one environment type.
Regularity enumeration can measure complexity {complexity theory}| [Kauffman, 1993].
Algorithm classes require time ranges {computational complexity theory}.
System complexity measures {algorithmic information content} {algorithmic complexity, system} {Kolmogorov complexity, system} can be numbers of bits for smallest program that can run on universal Turing machines and produce same output.
algorithm
Programs produce output from input and algorithm. Theory predicts facts from data and formulas. Algorithms and formulas are similar.
number
Random numbers have programs about as long as themselves. Information has no redundancy and cannot compress {irreducible information}.
proof
Infinitely many mathematical results require algorithms or proofs as large as output and so have no useful proofs. For example, axioms have no proof. Therefore, the principle of sufficient reason is not always true.
In general, whether programs will stop, or not, is impossible to predict {halting problem}|, as shown by Turing.
Turing machine
Turing machines must have at least one rule that leads to STOP, must not move to non-existent state, must use and make only coded sequences of marked and blank squares, and must have at least one marked square on output side. Turing machines have input and rules. Number of Turing machines and number of inputs are both infinite.
Many Turing machines never reach STOP.
If people can prove that Turing machine with some input reaches or does not reach STOP, people can make complex Turing machines that include that Turing machine and answer the question whether Turing machine stops. People can program complex Turing machines to make same mark, as long as that Turing machine does not stop. Complex Turing machine can include all Turing machines, so then all Turing machines can mark definite answers for inputs, whether they stop or not. Therefore, one algorithm decides same Turing machine reaches STOP, and one algorithm decides same Turing machine does not reach STOP. However, only one algorithm is true, and the other is false. Therefore, it is impossible to prove that Turing machines will reach STOP.
halting problem
Possible Turing machines have representations as natural numbers. Possible inputs have representations as natural numbers. If numbers of inputs and machines are equal, a square natural-number array can represent all possible Turing machines and inputs. See Figure 1.
Look at sequence, to take diagonal slash, on square-array main diagonal. See Figure 2.
Change marks for numbers in diagonal sequence. See Figure 3.
This sequence is not the same as any row or column sequence, because it differs from first row and column at first number, differs from second row and column at second number, and so on. If halting problem is solvable, this sequence can represent possible Turing machine/input combination, because first part can be legitimate Turing machine and second part can be legitimate input. However, array must contain all possible sequences, because array has all possible Turing machines and all possible inputs. Contradiction makes halting problem not solvable in general.
omega
Programs have halting probabilities {omega, number} {Chaitin number}. Data bits can be input to program until program does not request another bit, because it has stopped. Random-bit input stop program after different numbers of input bits. Probability that program stops is 0.5 raised to number of bits. To find total halting probability, add random-input-experiment probabilities. Using more random-input experiments can approach omega.
Process or system complexity can be number {logical depth}| {depth of argument} of steps from original input to final output [Bennett, 1988] [Herken, 1988] [Norretranders, 1998] [Goodwin, 1994] [Kauffman, 1993] [Koch and Laurent, 1999] [May, 1976] [Pagels, 1988] [Prigogine and Nicolis, 1989] [Prigogine and Stengers, 1984] [Prigogine, 1980] [Smale, 1967]. Steps can be logical steps from premises to conclusions, cause-and-effect relationships, or algorithm steps.
Phase-space points {strange attractor}| can be, not equilibria or periodic loops, but infinitely long lines in confined regions. Strange attractors are stable, can have few dimensions, and are periodic but not exactly periodic.
Stationary or moving cameras capture images, and associated hardware and software perform image analysis to find features, align images, extract descriptors and objects, and classify objects and motions {computer vision}.
Two points, in image or in physical or mathematical space, or two corresponding points, on two simultaneous images from two stereo cameras or on successive images from same camera, have distances {Euclidean distance} between them.
Signals {monogenic signal} can have phase, distance, time, orientation, or amplitude information.
Image object parts typically hide other object parts, so objects have visible parts and hidden parts {visibility problem}. Object-recognition algorithms recognize objects using parts. Image-generation algorithms show nearest object parts.
Three-dimensional space has volume pixels {voxel}. Voxels can be opaque, translucent, or transparent. Voxel transparency level can be a parameter {integral alpha}. Perceived pixel color P depends on integral alpha, voxel color intensity A, and background pixel color intensity B: P = alpha * A + (1 - alpha) * B, where A and B are red, green, or blue. Integral alpha is the same for all three color channels. For transparent voxels, alpha is zero, perceived color is background color, and voxel has no effect. For opaque voxels, alpha is one, perceived color is voxel color, and background has no effect. Therefore, systems can multiply alpha and voxel and background colors {premultiplied alpha} before compositing, for efficiency.
Volumetric displays can have multiple parallel display planes or a rotating plane to sweep out volume.
Computer vision uses image-capture-and-processing algorithms {computer vision algorithms} to find features and objects.
image capture
Cameras capture images pixel by pixel, with white, red, green, or blue intensity. Image algorithms can rotate, change dimensions, enhance brightness, and enhance contrast.
counting pixels
Counts light or dark pixels.
thresholding
Converts gray to black or white.
segmenting
Locates or counts textures and/or parts.
detecting edges
Finds object edges.
discovering blobs
Inspects image for connected white or black pixels to establish image reference points and regions.
recognizing components
Extracts simple three-dimensional geometric figures from image.
recognizing patterns
Locates features or objects, which may have different rotations or sizes and overlap or occlude each other.
Image points belonging to same feature are near each other. Parameter-space points belonging to same or similar features are near each other. Nearest neighbors can form point, line, or angle clusters {clustering algorithm}. Nearest-neighbor algorithms measure Euclidean distance, or other distance metrics, to find nearest-neighbor points and make clusters. Using distance measure can group features.
types
Clustering algorithms include hierarchical, self-organizing maps, K-means, fuzzy C-means, and expectation maximization. Error-weighted clustering retrofits clustering algorithms to use error-propagation information.
Self-organizing maps can group into equal categories.
process
Clustering can start with all features in one category and split features off {divisive clustering} or start with individual features and group them into classes {agglomerative clustering}. Clustering can use feature information to start or modify clustering {supervised clustering} or use only distances {unsupervised clustering}.
distance metric
Different hierarchical clustering methods use different ways to calculate distance between two clusters.
Minimum distance between cluster features {nearest-neighbor clustering} {single-linkage clustering} makes loose clusters with long branches containing few samples. Maximum distance between cluster features {furthest-neighbor clustering} {complete-linkage clustering} makes tight similar-size clusters with short branches.
Clustering can use average or median distance between features {unweighted pair-group method average} (UPGMA) or weighted-average point {centroid, cluster}.
For widely varying cluster sizes, average distance between features has weight {weighted pair-group average}: cluster feature number.
Clustering can use distance between cluster averages {within-groups clustering}.
distance metric: city-block distance
Distance measure between structure-space points is the same as Manhattan distance.
distance metric: Lp-metric
Distance measure between structure-space points is the same as Minkowski distance.
distance metric: Mahalanobis distance
Structure-space points have distances between them.
distance metric: Manhattan distance
Distance measure between structure-space points is the same as city-block distance.
distance metric: Minkowski distance
Distance measure between structure-space points is the same as Lp-metric.
supervised method
Classification can use already known patterns and clusters.
hierarchical clustering
Unsupervised, agglomerative clustering method {hierarchical clustering} measures distances between all points and places features in cluster hierarchy that looks like tree diagram {dendrogram, clustering}. Hierarchical clustering can make hierarchies and assign shared feature. Single features, and feature groups, are clusters. After calculating distance for cluster pairs, the closest clusters merge into one cluster, reducing cluster number by one. After calculating distance again for cluster pairs, the closest clusters merge into one cluster, and so on, until all features are in one, top-level cluster. Hierarchical clustering methods include centroid linkage, complete linkage, single linkage, and Ward's method. Ward's method calculates cluster mean and sum of squared differences from mean, for all cluster points. The next cluster is pair that gives smallest increase in sum of squared differences.
non-hierarchical clustering
Features can also be in different classes with no hierarchy {non-hierarchical clustering}.
non-hierarchical clustering: k-means clustering
Non-hierarchical, unsupervised method places features into a fixed number of clusters. First, it randomly assigns features to clusters. It calculates distances between feature pairs in cluster to find average cluster expression vector. It calculates distances between cluster pairs using average cluster expression vector. Features move to other clusters in turn, and method calculates all feature distances. Features stay in new cluster if distances between cluster feature pairs and between cluster pairs decrease.
Supervised k-means clustering first assigns features to clusters based on feature information and then proceeds as for unsupervised k-means clustering.
non-hierarchical clustering: self-organizing map
Non-hierarchical, unsupervised method places features in cluster based on nearness to cluster reference vector. First, cluster number is set. Starting from random vector, cluster reference vector converges by better partitioning feature data. It calculates distances between each expression vector and reference vectors and assigns feature to one cluster.
non-hierarchical clustering: principal component analysis
Non-hierarchical, unsupervised methods {principal component analysis, vision} (PCA) {singular value decomposition, vision} can combine feature dimensions linearly to reduce expression-space dimensions, remove redundancy, and average data. Similar unsupervised linear methods {factor analysis, computer} (FA) can look for significant factors in factor sets and find one, two, or three combined factors. It includes principal component analysis, correspondence analysis, spectral mapping, and non-linear mapping. Another similar technique {principal coordinate analysis} combines coordinates to make fewer dimensions. PCA, factor analysis, and principal coordinate analysis project data onto lower-dimension space by eliminating dimensions and dimension combinations with low significance. Number of remaining dimensions gives number of clusters to use for k-means clustering or self-organizing maps.
non-hierarchical clustering: support vector machine
Supervised clustering methods can use feature-vector training sets, group similar-function features into clusters, and group other-function features outside cluster. It tries to find cluster-specific features. Test features are in or outside cluster.
Features split space into two regions by making boundaries {hyperplane}. Hyperplanes can partition features so regions {soft margin} near hyperplanes have ambiguous examples.
Features can partition higher spaces {feature space}, mapped from feature vectors. Feature-space distances are metric and use special function {kernel function}. The best partition typically increases kernel function from simple to complex.
class analogy
Class analogy is a SIMCA method.
cluster sampling
Sampling can be from clusters equally.
cluster significance analysis
Using discrete or continuous data and embedded data can put compounds into groups by activity level. CSA locates small clusters in large spaces.
Cone and Hodgkin similarity index
Method measures molecular similarity.
discriminant-regression model
Model locates small clusters in large spaces.
distance-b program
Method locates small clusters in large spaces.
Jarvis-Patrick method
Structures can cluster in large databases by rating different features by similarity.
k-nearest neighbor
Supervised method calculates new object distance from all other objects to locate small clusters in large spaces.
partitioning
Process merges individuals into groups or splits whole into clusters.
similarity measure
Value can compare distances.
single-class discrimination
Method locates small clusters in large spaces.
Soft Independent Modeling of Class Analogies (SIMCA)
Supervised method uses model to find region boundaries or envelopes and locates small clusters in large spaces.
trend-vector analysis
Using activity and descriptor correlation vector ranks different features by similarity.
Image regions have sub-regions, which have different numbers of same-intensity pixels. Matrices can represent regions, and matrix cells can represent sub-regions. Cell values are number of same-intensity pixels. Matrices then have differences between cell sub-region values {Haar-like feature}, and matrices represent wavelets {Haar wavelet}. Regions are clusters or neighborhoods, such as rectangles or spheres, and so each region type has unique wavelet. Region sets have waves.
Images have points that do not cluster and do not belong to features. Outlier algorithms {outlier algorithms} use linear regression and best-fit to find outliers and discard them.
Methods {Potts model} can minimize energy by making two states either equal or unequal, with constant penalty for unequal and no penalty for equal.
Message-passing labeling inference algorithms {belief propagation} can compute many graphical-distribution statistics, each with few values, to calculate disparities by finding large-neighborhood minima. Belief propagation uses sum-product to find minimum or max-product to find maximum a posteriori (MAP) estimate. For stereo vision, Markov random-field model describes disparity, and inference algorithm determines nodes.
Algorithms {binary space partitioning} (BSP) can recursively divide space or polygon into two regions using hyperplanes, to make halves, quarters, eights, sixteenths, and so on.
orientation
Hyperplanes can have any orientation, making unequal regions. Hyperplanes that cut at medians make both regions equal.
polygons
Polygons can have angles greater than 180 degrees {reflex angle, polygon} or less than 180 degrees. Dividing polygon recursively makes regions with angles less than 180 degrees {convex set}.
recursion
Recursion steps define trees {BSP tree} and make stored lists {visibility list} that order polygons from front to rear. Convex sets become smaller until they include only point {BSP-tree leaves}.
multiple hyperplanes
Binary space partitioning can use hyperplane pairs or triples for cuts. Hyperplane pair divides space into four regions {quadtree}. Hyperplane triple divides space into eight regions {octree}.
Methods {iterative closest points method} can use point-sample clouds to align two images.
Modified BSP-tree algorithms {kd-tree} {k-dimensional tree} can use only hyperplanes perpendicular to space axes and use axis sequences, typically splitting at axis or polygon medians. If space has k axes, kd-tree has k cuts and tree branchings. kd-tree algorithms are better for searches using nearest neighbors, because they match space coordinate parameters and split hyperplanes go through points. Because hyperplanes are across axes, all regions have nodes or points.
Gauss-Helmert methods can use least squares {least-squares adjustment} to estimate best fit.
Painters paint background first, then layer objects on canvas from rear to front {painter's algorithm}, drawing over things that become behind.
Stereo images project onto aligned image plane by transformation {rectification of image}.
Cameras can use epipolar transform and absolute conic image in Kruppa equation to find standard metric {self-calibration}.
Robots can find their locations in environments {self-localization}, using self-localization alignment methods (SLAM).
Algorithms {z-buffering} {depth buffering} can store object-part depths for image generation or object recognition. z-buffers {depth buffer} represent two-dimensional images, for object identification. z-culling algorithms compare object-part depths and store object with smallest depth in buffer. The same visual angle covers more space farther away. To control for increasing spread with increasing distance, use variant w-buffers.
Feature detection can use point matching based on feature or boundary matching {feature detection methods}: corner detection, scale-invariant features (SIFT), and speeded-up robust features (SURF). Features are good image-category descriptors.
Algorithms {feature detection algorithms} can detect features.
descriptor
Properties {X-variable, vision} {X descriptor, vision} can describe features and have components.
canonical factor analysis
Factor analysis has a basic method.
centroid method
Factor analysis can use centroids.
Correlation Analysis
Properties and features have relationships.
correspondence factor analysis
Factor-analysis methods can use variable frequencies relative to properties, find chi-square values, and find principal components.
disjoint principal component
Principal components can be independent.
eigenvalue-one criterion
Thresholds can be how many components have eigenvalues greater than one.
eigenvector projection
Unsupervised linear methods can find factors.
Evolutionary Programming
Models can add and subtract randomly selected variables, with crossing-over, and evaluate for "fitness" or best fit. Extinction can happen more or less frequently or in more or fewer species. More-frequent extinctions have fewer species. Values follow power laws, because events can cause few or many extinctions.
evolving factor analysis
Methods can analyze ordered data.
explained variance percentage
Methods can indicate component number required to reach 90% of total variance.
factorial design
Designs can try to ensure design-space sampling, even if one position varies.
Genetic Function Algorithm
Linear property sets can have different values, change values by crossing-over between related genes, and have random changes, to select best fit.
latent variable
Variables can be linear descriptor combinations.
linear discriminant analysis
Supervised methods, in which boundary surface minimizes region variance and maximizes between-region variance, can put compounds into groups by activity level.
linear learning machine
Supervised methods can divide n-dimensional space into regions using discriminant functions.
maximum-likelihood method
Factor-analysis methods can find factors.
multidimensional scaling
Metric or non-metric methods can analyze similarity or dissimilarity matrices to find dimension number and place objects in proper relative positions.
multivariate adaptive regression spline
Non-parametric methods can find factors.
Mutation and Selection Uncover Models
Models can add and subtract randomly selected variables, with no crossing-over, and evaluate for "fitness" or best fit. Low mutation rates allow natural selection to operate on populations to move toward fitter genotypes. Intermediate mutation rates cause population to move toward and away from fitter genotypes. High mutation rates make many genotypes with direction, so high mutation blocks selection processes.
For any mutation rate, if gene number is too great, change rate is too great, and organism becomes extinct {error catastrophe, extinction}. Therefore, gene number has a limit if organisms do not make new species or find new environments.
Perhaps, cells and ecosystems also have upper limits to complexity. Complexity can increase with migration or speciation.
non-linear iterative partial least squares
Unsupervised linear methods can represent data as product of score matrix, for original observations, and loading-matrix transform, for original factors.
non-linear mapping
Topological mapping factor-analysis method uses linear variable combinations to make two or three new variables.
predictive computational model
Property information can predict behavior.
principal-component analysis
Variable principal components can be linear-descriptor combinations. Unsupervised linear methods can represent data as product of score matrix, for original observations, and loading-matrix transform, for original factors. PCA factor-analysis method uses linear variable combinations to make two or three new variables. PCA reduces unimportant variables.
principal-component regression
Singular-value decomposition can find singular-value sets to predict and project regression to latent structures.
principal factor analysis
Modified PCA can find principal factors.
Procrustes analysis
Methods can identify similarity descriptor sets.
QR algorithm
Methods can diagonalize matrices.
rank annihilation
Unsupervised linear methods can find factors.
response-surface method
Three-level designs can have three factors that quantify response and factor relationships. RSM includes MLR, OLS, PCR, and PLS linear designs, non-linear regression analysis, and non-parametric methods such as ACE, NPLS, and MARS.
Scree-plot
Residual variance approaches constancy, and plotted slope levels off, depending on number of components {Scree-test, vision}.
singular-value decomposition
In unsupervised linear methods, correlation matrix can become product of score, eigenvalues, and loading matrices, with diagonalization using QR algorithm.
spectral-mapping analysis
Factor-analysis methods can first take data logarithms to eliminate outliers and then subtract means from rows and columns, to leave only variation, showing which variables are important and how much.
structure space
Spaces can have two or three principal components.
target-transformation factor analysis
Methods can rotate features to match known patterns, such as hypotheses or signatures.
Unsupervised Method
Factors and response variables can relate, without using factor information or predetermined models.
Methods {eight point algorithm} can find structures from motions.
People can recognize six basic facial expressions {facial expression recognition}: anger, disgust, fear, happiness, sadness, and surprise. Expressions have unique muscle activities {Facial Action Coding System}, grouped into Action Parts. Methods detect faces, extract features, and classify expressions. Classifying can use Gabor filters, Bézier volumes, Bayes and Bayesian network classifiers, and Hidden Markov Models.
Gaussian filtering {Kalman filter} can use mean and variance parameters for normal distributions and can increase feature or pixel gain. Kalman filters are parametric, as opposed to particle filters. Kalman filters predict output from input.
First computer-vision stage is to find features, including invariants {local image analysis}. Invariants can be angles, local phase, and orientation.
Distributions can have representations as finite numbers of samples {particle, sample} defined on Markov chains {particle filtering}, rather than using parameters.
Operators {Sobel edge operator} can detect edges.
Methods {support-vector machine} can detect shapes from image segmentation, using color, shape, and distances.
Image features make maxima in parameter spaces. Algorithms {hill-climbing methods} can find local maxima that exceed threshold amount. If maximum is at feature parameter-space location and exceeds threshold, algorithm states that feature is in image and identifies location. Hill-climbing methods can become stuck at local maxima and fail to find more-important maxima.
Hill-climbing algorithms {Broyden-Fletcher-Goldfarb-Shanno method} (BFGS method) can improve quasi-Newton method.
Hill-climbing algorithms {Newton's optimization method} {Newton optimization method} can solve unconstrained non-linear optimization problems using function second-order partial-derivative Hessian square matrices, to find local maxima at locations where derivatives become zero.
Hill-climbing algorithms {quasi-Newton method} can simplify Newton's optimization method by simplifying Hessian matrix.
Hill-climbing algorithms {watershed algorithm} can find maximum gradient from center pixel to eight surrounding pixels and move to pixel with maximum gradient. If new pixel is minimum or is lower than threshold, stop and assign original pixel to same group as second pixel. If new pixel is not minimal and is not lower than threshold, find maximum gradient from second pixel to eight surrounding pixels and move to pixel with maximum gradient.
Algorithms {image processing algorithms} can determine background, cluster, check error and noise, find fiducials, normalize, check crosstalk, find signals, find features, aggregate replicates, and perform statistical analysis. Statistical cluster analysis can identify classes and assign shared feature. Hierarchical clustering can cluster into hierarchies. Self-organizing maps can group into equal categories.
Determining background {background determination algorithm} involves surface-fitting algorithm that detects global background changes across array. Background subtracts from features. Algorithm finds variance within feature integration aperture after global correction. Using average feature density can overestimate background. Putting space between feature blocks can find background.
Algorithms {error model algorithm} can check feature-signal noise, measure background variance, find cross-hybridization, check for spatial crosstalk and spectral crosstalk, measure normalization variation, and study replicates. Error model weights optimize signal-to-noise ratio. It has confidence value. Error flags label too-high variance, hybridization-control variance, high background, rejected pixels, bright neighbors, too-low signal-to-noise ratio, and saturated pixels.
Fiducials {fiducial-finding algorithm} are marks or shapes every 300 pixels, for automatic spot finding and row and column counting, without using quantitation-control scheme. Fiducials must be easy to distinguish from other image features and artifacts. Spotting and shrinking cause non-linear distortions and determine fiducial frequency needed. Row and column drift must be less than half the distance, five or six pixels, between features.
To account for labeling-amount, dye, fluorescent-detection, spotting, RNA-concentration, and sample-quantity differences, systems modify intensities {normalization, results}. Normalization allows comparison among slides and cell extracts.
types
Normalization can normalize on total intensity. Normalization can normalize on means and use ratio statistics. Normalization can use linear regression. Non-linear regression includes local regression, such as Locally Weighted Scatterplot Smoothing (LOWESS). Normalization algorithms use dilution-series controls, dye selection, filter selection, dye-quenching non-linearities, multiple gain settings, photobleaching amounts, and array-to-array normalization.
Strong signals at features can spread to neighboring features and skew weak signals. Features must be far enough apart to prevent more than 0.1% spatial crosstalk. Algorithms {spatial crosstalk mitigation algorithm} can reduce number of strong signals adjacent to weak signals. Algorithms can weight intensity sum across feature depending on neighboring features. Algorithms can use deconvolution with particular instrument.
Algorithms {signal integration algorithm} {signal quantitation algorithm} can use median pixel, integrate intensity, or use pixel-ratio median to generate values. First, algorithm aligns channels, if necessary. Fixed aperture is in both channels. Simultaneous scanning in both channels reduces crosstalk and allows pixel-to-pixel regression, which is more robust to defects. Integration can be only for high signal-to-noise pixel subsets.
Finding sites {spot-finding algorithm} can use three methods: find isolated peaks, align grid, or align centroid. To find isolated features or peaks, first shrink image to convolve it with feature model and then find isolated peaks. To align grid, first find fiducials and then fit rows and columns. To align centroid, first move off grid and find intensity-weighted centroid, if signal-to-noise feature ratio allows.
Algorithms {probe aggregation algorithm} {replicate aggregation algorithm} can average replicates.
Algorithms {prediction algorithms} can predict.
predictors
Factors, properties, or structures contribute to response values.
variable influence on prediction
Methods {variable influence on the prediction} can determine variable importance.
principal property
Variables {principal property} can be linear descriptor combinations.
non-parametric algorithms
Non-parametric algorithms can have alternating conditional expectations. Non-parametric methods {non-linear partial least-squares, vision} can find least squares.
outlier algorithms
Normal-distribution-outlier tests {Dixon's Q-test, vision} can measure ratio of smallest and largest differences.
Normal-distribution outlier tests {Grubbs' s-test, vision} can compare absolute values, of differences between mean and value, divided by standard deviation, to T distribution value.
network
Kohonen topology-preserving network mappings can retain topology. Topological indexes can represent graphs as numbers. Topological Tanimoto indexes can represent graphs as numbers.
rule induction system
IF/THEN statements {rule induction system, vision} can make output from input.
Factors, properties, or structures can correlate with response values {regression algorithms}.
regression
Regression analysis finds property and structure relationships. Multiple linear regression measures linear-component dependence on properties and finds descriptor coefficients. Non-linear regression is a parametric method that finds descriptor coefficients. Ridge regression is another regression method.
correlation
Factors can correlate, with correlation coefficients. Variance-covariance matrices {correlation matrix, vision} are complete, symmetric, square matrices that use property values and structure values, which can scale to normalize data. Partial least-squares can simplify variance-covariance matrix {matrix diagonalization, vision} {matrix bidiagonalization method, regression}.
Spearman rank correlation coefficient can measure molecular similarity.
least-squares
Ordinary least-squares {classical least-squares, vision} {least-squares regression, vision} {linear least-squares regression, vision} {multiple least-squares regression, vision} {multivariate least-squares regression, vision} can find descriptor coefficients by minimizing distances between values and regression line. Inverse least-squares inverts fitting method.
adaptive least-squares
Adaptive least-squares modifies ordinary least-squares by weighting or classes.
adaptive least-squares: fuzzy
Features can be in different classes with different weights.
partial least-squares
PLS uses least-squares to find independent variables and dependencies among variables. PLS maximizes latent-variable and observable covariation. PLS diagonalizes variance-covariance matrix. Multi-block PLS uses groups. Kernel algorithm is about covariation.
partial least-squares: Comparative Molecular Field Analysis
Partial least-squares methods (CoMFA) can analyze grids around sites and find grid-point interactions, to make sampled-point descriptors.
partial least-squares: Generating Optimal Linear PLS Estimations
GOLPE uses PLS and D-optimal design to select variables and then cross-validates.
partial least-squares: SAMPLS algorithm
Partial least-squares and trend vector analysis can work together.
non-least-squares
Non-least-squares methods can detect non-linear relationships.
Statistics has algorithms {statistical algorithms}.
best linear unbiased estimation
Estimates can give smallest variances among estimators.
mean square error
SSE / (observation number + factor number - 1).
SSE
Errors or residuals cause sum of squares of differences between observed and predicted responses.
SSR
Regression causes sum of squares of differences between observed and mean.
SST
Sum of squares of differences between predicted and mean makes total: SST = SSE + SSR.
standard error
Standard error is MSE square root.
Transforms {Hilbert transform} can be for one-dimensional signals.
Features have parameters, such as length, angle, color, distance, radius, and angle. Parameters have continuous-value ranges, such as lengths from millimeters to meters, or discrete-value sets, such as color categories. Features have parameter values that make vectors. For example, if parameter number is four, features have four-vectors, such as (0, 0, 0, 0), (3, 0, 0, 0), or (4, 2, 1, 3).
space
Hough spaces have dimension number equal to parameter number. In the example, Hough space has four coordinates. Hough space points can represent features.
feature extraction
Objects whose feature vector lies near feature point have that feature.
feature extraction: accumulator
Feature extraction can use voting {Hough transform}, to accumulate weights at feature points in Hough space {accumulator space} (Paul Hough) [1962]. After voting, if weight passes threshold at feature point, image has feature.
lines
Parameterized standard line, circle, or ellipse test sets establish feature-point coordinates in accumulator space. For lines, accumulator space can use polar-coordinate radius and angle. Edge-detector algorithms can pre-process images to find edges. Hough transforms can group edge points into lines, circles, or ellipses for identification (Richard Duda and Peter Hart) [1972] (Dana H. Ballard) [1981].
Transforms {pyramid transform} can be for three-dimensional signals and takes high-resolution images and makes low-resolution images.
One-dimensional Hilbert transforms {Radon transform}, at specific orientations, can transform multi-dimensional signals.
Transforms {Riesz transform} can be for two-dimensional signals.
Methods {validation algorithms} can check correlations, predictions, and designs.
bootstrapping validation
Method can use only internal data.
external validation
Other data can pair with model to predict activity.
cross-validation
For all data subsets, algorithm {leave-one-out, vision} {leave-groups-out, vision} can remove data subset and calculate remainder, such as for drug validation.
cross-validation: correlation coefficient
Method can validate and predict data.
fitness function
Validation method {lack-of-fit method} {jackknife validation method, vision} can measure fit, such as for drug validation.
Fisher F-test
Validation method can use F test.
other methods
Methods can be for drug validation {predictive residual sum of squares, vision} {scrambling dependent Y-values, vision} {standard deviation method, vision} {standard error of predictions, vision} {standard error of regression, vision}.
Brain theories {neural modeling} {brain theory} {computational neuroscience} model membrane currents, chemical changes, network oscillations, microcolumns, macrocolumns, and cell configurations to study learning and memory (Eric L. Schwartz).
viewpoint dependence
Real vision stores different viewpoints and matches similar schema.
single-neuron models
Neuron membranes have fast sodium-ion out-currents and later slower potassium-ion in-currents, as well as calcium ion, chloride ion, and other chemical flows, which affect action potential, adaptation, and shunting.
Dendrites and axons have structures and patterns.
Synapses have ion and chemical flows.
synapse plasticity
Synapse structure and physiology change over time with electrical and chemical flows. Feedback can alter weights in Hebbian learning.
More stable synapses learn and forget slower. Less stable synapses learn and forget faster. Systems use slow and fast plasticity combinations.
neural coding
Neurons have preferred stimuli. Neural coding can use instantaneous or average impulse frequency for rate coding. Impulses can code intensity, which can represent stimulus amplitude or stimulus probability.
Neuron signaling uses minimal number of impulses to convey information (Horace Barlow).
neural inhibition and excitation
Inhibition can subtract or divide. Excitation can add or multiply. Adding and subtracting accumulate same stimulus type, to pass or not pass threshold and determine whether to perform action. Multiplying and dividing represent stimulus interactions and feature pairing, to allow object detection or recognition.
neuron development
Neurons, axons, and dendrites migrate and grow. Migration and growth use hormone and growth-factor chemical gradients. For efficiency, wiring patterns are optimal in spacing and number {minimal wiring hypothesis}.
Sense physiology uses Bayesian inference, to reflect conditional rules.
neural networks
Neurons connect specifically to each other and use recurrence. Models use neuron pairs.
memory
Memory can be associative or content-addressable. Hippocampus models are for long-term memory. Prefrontal-cortex models are for working memory. Memory can use phase synchrony and wave resonance.
Electrical cables have resistance and capacitance, which determine oscillation time and dissipation length. Partial differential equations (William Thompson) are similar to wire heat-conductance equations (Fourier). Dendrites, cell bodies, and axons are like cables and have capacitances and resistances in parallel and series {cable theory} (Wilfrid Rall). Fibers have resistance because cytoplasm and membrane are not good conductors. Fibers have capacitance because membrane phospholipid bilayer does not conduct but has charge polarization.
Functions {Gabor function}, derived from neuron response frequencies, can represent neuron location, width, length, orientation, and frequency as wavelet. Gabor functions represent neuron types. Neural nets or systems are Gabor-function configurations.
Units representing neurons can have binary outputs off or on, use input thresholds, and be in networks. Neural networks {Hopfield net} (John Hopfield) can use recurrence to iteratively determine final values.
convergence
Outcomes are locations and have values. Hopfield nets converge on local minima among set.
training
Training with images can determine locations that represent standard features or objects.
recognition
If local minimum matches location representing feature, Hopfield net recognizes feature in images. In particular, input that is only feature index or cue can lead to the feature, so Hopfield nets can act like memory system {content-addressable memory, Hopfield net}.
Statistical-mechanics models {Ising model} can use pairs of +1 or -1 spins (Ernst Ising) [1925]. Pair spins can have same or different alignment. Pair energy is product of spins: +1 * +1 = 1 = -1 * -1, or +1 * -1 = -1 = -1 * +1.
Network can show spin interactions. Nodes are particles with spins, and connection edges are interaction energies. Regions, and whole systems, have total energy and are system states.
Neural nets have binary units, +1 and -1, as nodes and have connections among neurons. Total energy is system state.
Geometry represents Euclidean space as n-dimensional sphere {conformal geometry}, not as vector space. Operations are linear. It has projective geometry.
Stereo-vision constraints {epipolar constraint} can reduce searching to along image curve {epipolar line}, using fundamental matrix, which gives camera relative orientation and position, or essential matrix, which describes epipolar geometry using focal length, chip size, or optical-center coordinates. Other camera has focal-point projection {epipole}. First-camera pixels have corresponding pixels on second-camera epipolar line.
Images have vertical orthogonal planes {homography} at focal points.
The same scene point is at different pixel coordinates {disparity of images} in rectified images from two cameras, with distance between them. Disparity is directly proportional to depth.
Two images have disparities between corresponding pixels and have disparity-change rates {disparity rate}.
Image objects have special points, lines, or angles {image features}, whose enumeration or configuration can describe objects. Training on standard images can teach object features and configuration. Features have parameters, such as length, angle, color, and distance. Feature scale, noise, illumination, and distortion can differ.
Camera image can have virtual shapes superimposed on it {augmented reality}, to serve as landmarks or features.
Curves have models {curve functions}. Hyperbolas have curvature, arc length, and separation. Clothoid curves have arc length related to bending. G2-splines have arc length related to bending. B-splines are closed curves. Fifth-degree Cartesian polynomials are closed curves. Polar splines are closed curves.
Three-dimensional curves use ellipsoids, spheroids, cylinders, quartics, and splines and try to find optimum position, orientation, scale, and mathematical function.
Principal component analysis can find axes.
Image features {descriptor, image}, such as points and regions, relate to object recognition. Features can be independent or combine. Descriptors include binary, spatial, shape, texture, and local colors. Texture can be gradient location-orientation histogram. Corner detection, SIFT, and SURF use descriptors.
Three-dimensional spheres, cubes, cylinders, cones, and wedges {geon} can be object-representation components. Different geon types look different from different viewpoints {viewpoint-invariance, geon}. Occluded, overlapped, noisy, blurry, or deformed geon types look different from other occluded, overlapped, noisy, blurry, or deformed geon types {stability, geon}. Object representations have geons and relations among geons {recognition-by-components, geon} (Irving Biederman) [1987].
Small areas {Monge patch} can have three-dimensional image patterns.
Computer vision tasks {computer vision tasks} include content-based image retrieval, depth perception, egomotion, event detection, identification, image restoration, indexing, learning, object recognition, pose estimation, scene reconstruction, and tracking.
art gallery problem
Find minimum-length path through art gallery from which one can see all pictures. Watchman-route problem, safari problem, zookeeper problem, touring-polygons problem, and parts-cutting problem have same type. Rubberband algorithms solve them.
barcode reading
Decode 1D and 2D codes.
character recognition
Recognize serial numbers, words, and phrases.
content-based image retrieval
In image sets, find images with content, such as text, number, object, or image.
dense stereo vision
Two cameras, with known or unknown separation and angle, can find scene-point depths.
depth perception
One eye can use linear perspective, motion parallax, interposition, shading, relative size, relative height, aerial perspective, texture, and three-dimensional-structure motion. Two eyes can use convergence and binocular disparity.
egomotion
Calculate camera three-dimensional motion.
event detection
Find abnormal or special feature or property in images.
gauging
Measure object dimensions.
human-machine interface
Algorithms allow human and robot interaction.
identification
Match individual image to stored image.
image restoration
Remove noise using low-pass filters, median filters, or image models.
kinematic chain
Rigid bars connect by sliding or rotating joints.
object recognition
Recognize learned object type at image location.
optical flow
When camera or person moves, scene flows past. Lucas-Kanade method, Horn-Schunck method, Nagel-Enkelmann method, correlation method, and block-matching method use variational methods to find optical flow.
pose estimation
Find object position or orientation.
scene reconstruction
Using several scene images, calculate three-dimensional model.
structure from motion
Motions cause disparities and disparity rates, which can reveal structure. Bundle-adjustment algorithms can find three-dimensional scene structure and camera trajectories.
First, projective reconstruction can construct projected structure, then Euclidean upgrading can find actual shape. Affine reconstruction uses Tomasi-Kanade factorization.
template matching
Find, match, and/or count patterns.
tracking
Follow object velocities and directions.
Find minimum-length path through art gallery from which one can see all pictures {art gallery problems}. Watchman-route problem, safari problem, zookeeper problem, touring-polygons problem, and parts-cutting problem have same type. Rubberband algorithms solve them.
Two cameras, with known or unknown separation and angle, can find scene-point depths {dense stereo vision}.
Calculate camera three-dimensional motion {egomotion}.
Algorithms {human-machine interface} allow human and robot interaction.
Remove noise using low-pass filters, median filters, or image models {image restoration}.
Rigid bars connect by sliding or rotating joints {kinematic chain}.
When camera or person moves, scene flows past {optical flow, camera}. Lucas-Kanade method, Horn-Schunck method, Nagel-Enkelmann method, correlation method, and block-matching method use variational method to find optical flow.
Find object positions and orientations {pose estimation}.
Using several scene images, calculate three-dimensional model {scene reconstruction}.
Motions cause disparities and disparity rates, which can reveal structure {structure from motion}. Bundle-adjustment algorithms can find three-dimensional scene structure and camera trajectories. First part {projective reconstruction} can construct projected structure, and second part {Euclidean upgrading} can find actual shape. Affine reconstruction uses Tomasi-Kanade factorization.
Natural selection can work on differences to select optima {evolution theories}.
In fitness landscapes, starting from any genotype, change one allele randomly to go to neighboring genotype, and then stay there if it has higher fitness {adaptive walk}|. Adaptive walks go uphill to local peaks.
steps
After uphill steps, number of possibly higher steps becomes half or less and finding a higher step takes twice as long or longer.
If starting at low fitness, large steps work best. If starting at high fitness, small steps work best.
recombination
Recombination allows leaving local maximum to look for global maximum, if landscape is not too random.
few alleles
With two alleles for genes, number of steps to local peak is natural logarithm of gene number. Many local peaks are nearby. Because changes are random and neighboring fitnesses do not correlate, selection makes little improvement.
multiple gene changes
If several alleles change, steps go farther, and fitness-change range is greater.
gene number
If gene number increases, fitness increase per step is less.
Gene fitness can depend on other-gene fitness in same or other species {coupled fitness landscape} {fitness landscape, coupled}.
If species dependency is low, same-species gene dependency is high, or species number is low, system is stable. If species dependency is high, same-species gene dependency is low, or species number is high, system is unstable.
If species number or species-dependency level can change, species dependency tends to middle, to maximize average fitness and minimize average extinction rate. Middle level is just before point where too many changes happen.
Genes have alleles, which contribute to survival and reproduction {fitness, allele}.
fitness landscape
Graphs {fitness landscape, evolution} {genetic graph} show all genes and alleles in a genotype. Genotypes have height. Genotypes differ from neighboring genotypes by one allele.
correlations
Fitness landscapes can have neighbors with similar fitness {correlated fitness}, so allele fitness depends on other-gene fitness. If allele fitness greatly depends on other genes, allele change affects whole system, fitnesses are similar, and landscape has many local peaks. If genes affect all others, fitnesses are equal, as in random case. If allele fitness depends slightly on other genes, allele change affects small region, fitnesses are different, and landscape has few local peaks. Highest peaks have widest bases.
patch
Genetic graphs can divide into local maximum-fitness regions. Patch boundaries are at local fitness minima.
search
In fitness landscapes, search for maximum can stop at local maximum. To escape local maximum or minimum, methods can look at patches or ignore input from neighbors. Instead of moving from fitness-landscape point to point, trajectories can move from patch to patch, seeking highest maximum. If patch size is small, system takes many steps to reach maximum fitness, can move away from true maximum, and can change over time, so it never reaches maximum fitness. If patch size is large, patches can have several maximum-fitness peaks. Moderate patch size balances fitness and time. If fitness landscape is smooth, patches have no affect.
Systems can ignore input from neighbors and use input from farther away. If jumps are small, system takes many steps to reach maximum fitness, can move away from true maximum, and can change over time, so it never reaches maximum fitness. If jumps are large, system can jump several maximum-fitness peaks. Moderate jump size balances fitness and time.
Systems {genetic algorithm} can perform similar processes varying by one or more parameters, in response to environment situations that require learning. Some processes are more correct or successful and have better fitness. More-successful processes can continue by selection and/or initiate similar processes by reproduction. Systems thus move toward higher percentage of more-successful processes. Systems have evolution.
In Boolean systems {genetic circuit, mathematics} {genetic network model}, repressors can turn off gene expression. Enhancers can turn on gene expression. Genes are on or off. Repressors and enhancers are either present or absent. Boolean canalyzing functions model gene regulation. Without repressor, gene expresses. With derepressor, gene expresses. Different repressor or derepressor amounts can modulate gene expression. Promoter, derepressor, or other gene sites can regulate gene expression.
Manipulating molecules and atoms {nanotechnology}|, such as DNA, RNA, or protein strands, can create machines and programs. Cross-links and ratchets can make rotations and slides.
Amino-acid-like compounds {bis-peptide} {bis-amino acid} have two pairs, each with carboxyl and amino, on opposite sides for hexagon shape, 90-degree sides for square shape, or 60-degree sides for triangle shape, that can link to make peptide-like structures with different shapes.
Physical-unit interactions can order systems {self-organization}| {order for free}. Forces and interactions among individuals can result in complexes.
dissipative system
Open non-equilibrium thermodynamic systems input and output matter and energy. Examples are cells and organisms. Dissipative systems have no general laws. If systems have diverse elements that can interact to make new things in closed space, catalytic things can increase original reaction rates {autocatalytic system, self-organization}. System components can interact and organize into patterned subsystems by relaxation methods. Self-organization involves compensations and rearrangements among group parts. Interactions and patterns can cause groups to exhibit behavior not found in parts. Life exists between chaos and order, as at phase-transition boundary, because variation must not be too little or too much.
Systems that add matter and energy can be in states {self-organized criticality} in which catastrophe strikes large and small, in power-law relations.
Outline of Knowledge Database Home Page
Description of Outline of Knowledge Database
Date Modified: 2022.0225